//
//  XIGeometry.m
//  XIEngine
//
//  Created by Bazsi on 12.06.09.
//  Copyright 2009 Universität Basel. All rights reserved.
//

#import "XIGeometry.h"
#import "XIEngine.h"

#pragma mark Constants
/** Assign values to constant variables. **/

const XILine XILineZero = {0.0, 0.0};
const XILine XILineXAxis = {0.0, 0.0};
const XILine XILineYAxis = {INFINITY, 0.0};

const XILineSegment XILineSegmentZero = {{0.0, 0.0}, {0.0, 0.0}};

const XICircle XICircleZero = {{0.0, 0.0}, 0.0};
const XICircle XICircleUnit = {{0.0, 0.0}, 1.0};

#pragma mark -
#pragma mark Creator functions
/** Definition of creator functions. **/

XILine XILineMake(float m, float b)
{
    XILine l; l.m = m; l.b = b; return l;
}

XILine XILineThroughPoints(CGPoint point1, CGPoint point2)
{
	if(point2.x == point1.x){return XILineMake(INFINITY, point1.x);}
	float m = (point2.y - point1.y) / (point2.x - point1.x);
	return XILineThroughPointWithSlope(point1, m);
}

XILine XILineThroughPointWithSlope(CGPoint point, float slope)
{
	float b = point.y - slope * point.x;
	return XILineMake(slope, b);
}

XILineSegment XILineSegmentMake(CGPoint point1, CGPoint point2)
{
	XILineSegment s; s.a = point1; s.b = point2; return s;
}

XICircle XICircleMake(CGPoint c, float r)
{
	XICircle k; k.c = c; k.r = r; return k;
}

XICircle XICircleThroughPoints(CGPoint point1, CGPoint point2, CGPoint point3)
{
	XILine line1 = XILineThroughPoints(point1, point2);
	XILine line2 = XILineThroughPoints(point2, point3);
	CGPoint center1 = XIPointBetweenPoints(point1, point2);
	CGPoint center2 = XIPointBetweenPoints(point2, point3);
	XILine ortho1 = XILineOrthogonalToLineThroughPoint(line1, center1);
	XILine ortho2 = XILineOrthogonalToLineThroughPoint(line2, center2);
	CGPoint c = XILineIntersection(ortho1, ortho2);
	float r = XIDistanceBetweenPoints(c, point1);
	return XICircleMake(c, r);
}

#pragma mark -
#pragma mark Tests

BOOL XIPointExists(CGPoint point)
{
	return point.x == INFINITY || point.y == INFINITY ? NO : YES;
}

BOOL XILineExists(XILine line)
{
	return line.b == INFINITY ? NO : YES;
}

BOOL XICircleExists(XICircle circle)
{
	return !XIPointExists(circle.c) || circle.r == INFINITY ? NO : YES;
}

BOOL XILineSegmentExists(XILineSegment segment)
{
	return !XIPointExists(segment.a) || !XIPointExists(segment.b) ? NO : YES;
}

#pragma mark -
#pragma mark Points
/** Definition of fuctions. **/

float XIDistanceBetweenPoints(CGPoint point1, CGPoint point2)
{
	return sqrt(pow(point1.x - point2.x, 2) + pow(point1.y - point2.y, 2));
}

CGPoint XIPointBetweenPoints(CGPoint point1, CGPoint point2)
{
	return CGPointMake((point1.x + point2.x) * 0.5, (point1.y + point2.y) * 0.5);
}

#pragma mark -
#pragma mark Lines

BOOL XILineIsParallelToLine(XILine line1, XILine line2)
{
	return line1.m == line2.m;
}

BOOL XILineIsOrthogonalToLine(XILine line1, XILine line2)
{
	return line1.m * line2.m == -1.0;
}

BOOL XILineIntersectsLine(XILine line1, XILine line2)
{
	return line1.m != line2.m;
}

BOOL XILineIsTangentOnCircle(XILine line, XICircle circle)
{
	int nrOfIntersections = XICircleIntersectionWithLine(circle, line, nil);
	return nrOfIntersections == 1 ? YES : NO;
}

BOOL XILineEqualsToLine(XILine line1, XILine line2)
{
	return line1.m == line2.m && line1.b == line2.b;
}

BOOL XILineContainsPoint(XILine line, CGPoint point)
{
	return point.x == line.m * point.x + line.b;
}

CGPoint XILineIntersection(XILine line1, XILine line2)
{
	if(line1.m == line2.m){return CGPointMake(INFINITY, INFINITY);}
	float x = (line2.b - line1.b) / (line1.m - line2.m);
	float y = line1.m * x + line1.b;
	return CGPointMake(x, y);
}
	
CGPoint	XILineClosestPointToPoint(XILine line, CGPoint point)
{
	XILine ortho = XILineOrthogonalToLineThroughPoint(line, point);
	return XILineIntersection(line, ortho);
}

float XILineAngle(XILine line)
{
	if(line.m == INFINITY){return 90.0;}
	float a = atan(line.m);
	if(a < 0){a += 180.0;}
	return a;
}

float XILineAngleWithLine(XILine line1, XILine line2)
{
	float a = XILineAngle(line2) - XILineAngle(line1);
	return min(a, 180.0 - a);
}

XILine XILineParallelToLineThroughPoint(XILine line, CGPoint point)
{
	return XILineThroughPointWithSlope(point, line.m);
}

XILine XILineOrthogonalToLineThroughPoint(XILine line, CGPoint point)
{
	return XILineThroughPointWithSlope(point, -1.0 / line.m);
}

#pragma mark -
#pragma mark Line segments

BOOL XILineSegmentContainsPoint(XILineSegment segment, CGPoint point)
{
	XILine l = XILineThroughPoints(segment.a, segment.b);
	return XILineContainsPoint(l, point) && abs(segment.a.x - segment.b.x) >= abs(segment.a.x - point.x) + abs(segment.b.x - point.x);
}

CGPoint XILineSegmentClosestPointToPoint(XILineSegment segment, CGPoint point)
{
	XILine l = XILineThroughPoints(segment.a, segment.b);
	CGPoint p = XILineClosestPointToPoint(l, point);
	if(XILineSegmentContainsPoint(segment, p)){return p;}
	return XIDistanceBetweenPoints(point, segment.a) <= XIDistanceBetweenPoints(point, segment.b) ? segment.a : segment.b;
}

#pragma mark -
#pragma mark Circles

BOOL XICircleEqualsCircle(XICircle circle1, XICircle circle2)
{
	return CGPointEqualToPoint(circle1.c, circle2.c) && circle1.r == circle2.r ? YES : NO;
}

BOOL XICircleEdgeContainsPoint(XICircle circle, CGPoint point)
{
	return pow(point.x - circle.c.x, 2) + pow(point.y - circle.c.y, 2) == pow(circle.r, 2);
}

BOOL XICircleAreaContainsPoint(XICircle circle, CGPoint point)
{
	return pow(point.x - circle.c.x, 2) + pow(point.y - circle.c.y, 2) < pow(circle.r, 2);
}

BOOL XICircleContainsPoint(XICircle circle, CGPoint point)
{
	return pow(point.x - circle.c.x, 2) + pow(point.y - circle.c.y, 2) <= pow(circle.r, 2);
}

BOOL XICircleContainsCircle(XICircle circle1, XICircle circle2)
{
	return XIDistanceBetweenPoints(circle1.c, circle2.c) + circle2.r <= circle1.r;
}

int XICircleIntersection(XICircle circle1, XICircle circle2, CGPoint *intersections)
{
	float a, b, c, d;
	if(circle1.c.x == circle2.c.x)
	{
		if(circle1.c.y == circle2.c.y){return 0;} // There are no intersections if the centers of the 2 circles are the same.
		float y = (sq(circle1.r) - sq(circle2.r) + sq(circle2.c.y) - sq(circle1.c.y)) / (2 * (circle2.c.y - circle1.c.y));
		a = 1;
		b = -2 * circle1.c.x;
		c = sq(y) - 2 * y * circle1.c.y + sq(circle1.c.x) + sq(circle1.c.y) - sq(circle1.r);
		d = sq(b) - 4 * c;
		if(d < 0){return 0;}
		float x1 = (-b + sqrt(d)) / 2.0;
		float x2 = (-b - sqrt(d)) / 2.0;
		CGPoint i1 = CGPointMake(x1, y);
		CGPoint i2 = CGPointMake(x2, y);
		CGPoint i[2] = {i1, i2};
		*intersections = i[0];
		return x1 == x2 ? 1 : 2;
	}
	float u = (sq(circle1.r) - sq(circle2.r) + sq(circle2.c.x) + sq(circle2.c.x) - sq(circle1.c.x) - sq(circle1.c.y)) / 
		(2 * circle2.c.x - circle1.c.x);
	float v = (2 * circle1.c.y - 2 * circle2.c.y) / (2 * circle2.c.x - 2 * circle1.c.x);
	a = (sq(b) + 1);
	b = 2 * (u * v - v * circle1.c.x - circle1.c.y);
	c = sq(circle1.c.x) + sq(circle1.c.y) + sq(u) - 2 * u * circle1.c.x - sq(circle1.r);
	d = sq(b) - 4 * a * c;
	if(d < 0){return 0;}
	float y1 = (-b + sqrt(d)) / (2.0 * a);
	float y2 = (-b - sqrt(d)) / (2.0 * a);
	float x1 = u + v * y1;
	float x2 = u + v * y2;
	CGPoint i1 = CGPointMake(x1, y1);
	CGPoint i2 = CGPointMake(x2, y2);
	CGPoint i[2] = {i1, i2};
	*intersections = i[0];
	return x1 == x2 && y1 == y2 ? 1 : 2;
}

int XICircleIntersectionWithLine(XICircle circle, XILine line, CGPoint *intersections)
{
	float a = sq(circle.c.x) + 1;
	float b = 2 * (line.m * line.b - circle.c.x - circle.c.y * line.m);
	float c = sq(line.b) - sq(circle.c.x) - 2 * circle.c.y * line.b + sq(circle.c.y) - sq(circle.r);
	float d = sq(b) - 4 * a * c;
	if(d < 0){return 0;}
	if(d == 0)
	{
		float x = -b / (2 * a);
		float y = line.m * x + line.b;
		CGPoint i = CGPointMake(x, y);
		*intersections = i;
		return 1;
	}
	float x1 = (-b + sqrt(d)) / (2 * a);
	float x2 = (-b - sqrt(d)) / (2 * a);
	float y1 = line.m * x1 + line.b;
	float y2 = line.m * x1 + line.b;
	CGPoint i1 = CGPointMake(x1, y1);
	CGPoint i2 = CGPointMake(x2, y2);
	CGPoint i[2] = {i1, i2};
	*intersections = i[0];
	return 2;
}


int XICircleTangentThroughPoint(XICircle circle, CGPoint point, XILine *tangents)
{
	if(XICircleAreaContainsPoint(circle, point)){return 0;}
	if(XICircleEdgeContainsPoint(circle, point))
	{
		XILine helpLine = XILineThroughPoints(point, circle.c);
		XILine t = XILineOrthogonalToLineThroughPoint(helpLine, point);
		*tangents = t;
		return 1;
	}
	CGPoint middle = XIPointBetweenPoints(circle.c, point);
	float radius = XIDistanceBetweenPoints(middle, point);
	XICircle helpCircle = XICircleMake(middle, radius);
	CGPoint *intersections;
	int nrOfIntersections = XICircleIntersection(circle, helpCircle, intersections);
	if(nrOfIntersections < 2){return 0;} // This shouldn't occur, but for safety check the number of results to be sure there are 2.
	XILine t1 = XILineThroughPoints(point, intersections[0]);
	XILine t2 = XILineThroughPoints(point, intersections[1]);
	XILine t[2] = {t1, t2};
	*tangents = t[0];
	return 2;
}

float XICircleShortestDistanceToLine(XICircle circle, XILine line)
{
	CGPoint intersection = XILineClosestPointToPoint(line, circle.c);
	float distance = XIDistanceBetweenPoints(intersection, circle.c);
	return distance - circle.r;
}

#pragma mark -
#pragma mark Paths

XIPathNode XIPathNodeMake(CGPoint position, id *properties)
{
	XIPathNode n;
	n.p = position;
	n.properties = properties;
	return n;
}

XIPath XIPathMake()
{
	XIPath p;
	p.head = 0;
	p.tail = 0;
	p.properties = 0;
	return p;
}

BOOL XIPathPush(XIPath* path, XIPathNode node)
{
	if(!path){return NO;}
	XIPathEntry entry;
	entry.node = node;
	entry.next = path->head;
	if(path->head){path->head->prev = &entry;}
	path->head = &entry;
	return YES;
}

BOOL XIPathPop(XIPath* path, XIPathNode* node)
{
	XIPathEntry* entry = path->head;
	if(!entry){return NO;}
	*node = entry->node;
	path->head = entry->next;
	free(entry);
	return YES;
}

BOOL XIPathIsClosed(XIPath path)
{
	return path.head == path.tail;
}

int XIPathCount(XIPath path)
{
	int i = 0;
	XIPathEntry *entry = path.head;
	while(entry)
	{
		i++;
		entry = entry->next;
	}
	return i;
}

BOOL XIPathContainsPoint(XIPath path, CGPoint point)
{
	if(path.head == 0){return NO;}
	if(path.head->next == 0){return CGPointEqualToPoint(path.head->node.p, point);}
	XIPathEntry *e1 = path.head;
	XIPathEntry *e2 = path.head->next;
	while (e2)
	{
		XILineSegment segment = XILineSegmentMake(e1->node.p, e2->node.p);
		if(XILineSegmentContainsPoint(segment, point)){return YES;}
		e1 = e2;
		e2 = e2->next;
	}
	return NO;
}

CGPoint XIPathClosestPoint(XIPath path, CGPoint point)
{
	if(path.head == 0){return CGPointMake(INFINITY, INFINITY);}
	if(path.head->next == 0){return path.head->node.p;}
	float smallestDistance = INFINITY;
	CGPoint closestPoint = CGPointMake(INFINITY, INFINITY);
	XIPathEntry *e1 = path.head;
	XIPathEntry *e2 = path.head->next;
	while (e2)
	{
		XILineSegment segment = XILineSegmentMake(e1->node.p, e2->node.p);
		CGPoint p = XILineSegmentClosestPointToPoint(segment, point);
		float distance = XIDistanceBetweenPoints(p, point);
		if(distance < smallestDistance)
		{
			smallestDistance = distance;
			closestPoint = p;
		}
		e1 = e2;
		e2 = e2->next;
	}
	return closestPoint;
}

CGPoint XIPathTravelFromPoint(XIPath path, CGPoint point, float length)
{

}


